package org.chengn.level_hard.context2646;

import java.util.*;

/**
 * @Title: Context2646
 * @Author ChengN
 * @Package org.chengn.level_hard.context2646
 * @Date 2023/12/6 22:04
 * @description: 最小化旅行的价格总和
 */
public class Context2646 {
    int[] nodes = new int[50];
    List<Integer>[] nodeList = new List[50];
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        Map<Integer, List<Integer>> edgeMap = new HashMap<>();
        for (int i = 0; i < nodeList.length; ++i) {
            nodeList[i] = new ArrayList<>();
        }

        for (int[] keyValue : edges) {
            nodeList[keyValue[0]].add(keyValue[1]);
            nodeList[keyValue[1]].add(keyValue[0]);
        }

        for (int[] trip : trips) {
            Set<Integer> usedNodes = new HashSet<>();
            usedNodes.add(trip[0]);
            nodes[trip[0]]++;
            dfs(trip[0], trip[1], usedNodes);
        }

        int[] resList = dfs(0, new HashSet<>(), price);

        return Math.min(resList[0], resList[1]);
    }

    int[] dfs(int node, Set<Integer> usedNode, int[] price) {
        if (usedNode.contains(node)) {
            return new int[]{0, 0};
        }
        usedNode.add(node);
        List<Integer> thisWay = nodeList[node];
        int[] res = new int[]{price[node] * nodes[node], price[node] * nodes[node] / 2};
        for (Integer integer : thisWay) {
            int[] nodeRes = dfs(integer, usedNode, price);
            res[1] += nodeRes[0];

            res[0] += Math.min(nodeRes[0], nodeRes[1]);
        }
        return res;
    }

    boolean dfs(int node, int des, Set<Integer> usedNodes) {
        usedNodes.add(node);
        if (node == des) return true;
        List<Integer> nextNodeList = nodeList[node];
        for (Integer val : nextNodeList) {
            if (usedNodes.contains(val)) continue;
            nodes[val]++;
            if (dfs(val, des, usedNodes)) return true;
            nodes[val]--;
        }
        return false;
    }
}
